import java.util.ArrayList;
import java.util.List;

public class Solution93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans=new ArrayList<>();
        String[] temp=new String[4];
        dfs(0,temp,ans,0,s);
        return ans;
    }

    private void dfs(int k, String[] temp, List<String> ans, int last, String s) {
        if (k==3){
            String t=s.substring(last);
            if (valid(t)){
                ans.add(temp[0].concat(".").concat(temp[1]).concat(".").concat(temp[2]).concat(".").concat(t));
            }
            return;
        }
        for (int i=last;i<Math.min(s.length(),last+3);i++){
            if (valid(s.substring(last,i+1))){
                temp[k]=s.substring(last,i+1);
                dfs(k+1,temp,ans,i+1,s);
            }
        }
    }

    private boolean valid(String s) {
        if (s.length()>3 || s.length()==0){
            return false;
        }
        if (s.length()>1 && s.charAt(0)=='0'){
            return false;
        }
        int t=Integer.parseInt(s);
        return t>=0 && t<=255;
    }

    public static void main(String[] args) {
        System.out.println(new Solution93().restoreIpAddresses("25525511135"));
    }
}
